package gold.gold05;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 */
public class S1619水域大小 {
    /**
     * 95, 找到一个0就开始填充周围的0, 修改land数组, 不用每次都遍历查找第一个0, 查找0的时候从上一次发现0的下一个位置开始就可以了。
     * 复杂度为O(n^2), 这里每次都传参land, 但是即使把land变成全局变量, 对时间也没有影响, 这个传参并没有损失什么。
     */
    public int[] pondSizes(int[][] land) {
        List<Integer> record = new ArrayList<>();
        int row = land.length;
        int col = land[0].length;
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(land[i][j] == 0){
                    record.add(fillZero(land, i, j));
                }
            }
        }
        int[] res = new int[record.size()];
        for(int i = 0; i < record.size(); i++){
            res[i] = record.get(i);
        }
        Arrays.sort(res);
        return res;
    }
    private int fillZero(int[][] land, int row, int col){
        int rowPlus = land.length;
        int colPlus = land[0].length;
        int fillCount = 0;
        land[row][col] = 1;
        fillCount++;
        //int[] helpArr = new int[]{-1, 0, 1};
        for(int i = row - 1; i <= row + 1; i++){
            for(int j = col - 1; j <= col + 1; j++){
                if(0 <= i & i < rowPlus & 0 <= j & j < colPlus){
                    if(land[i][j] == 0){
                        fillCount += fillZero(land, i, j);
                    }
                }
            }
        }
        return fillCount;
    }
}
